package org.example;

public class Solution17 {

    public int firstMissingPositive(int[] nums) {
        int n = nums.length;

        // 1. 遍历数组，将小于等于0的数字替换为一个大于数组长度的数
        for (int i = 0; i < n; i++) {
            if (nums[i] <= 0) {
                nums[i] = n + 1;
            }
        }

        // 2. 标记位置上的数，如果出现过为负数，
        for (int i = 0; i < n; i++) {
            int num = Math.abs(nums[i]);
            if (num <= n) {
                nums[num - 1] = -Math.abs(nums[num - 1]);
            }
        }

        // 3. 找到第一个正数
        for (int i = 0; i < n; i++) {
            if (nums[i] > 0) {
                return i + 1;
            }
        }

        return n + 1;
    }

}
